package cn.lintcode;

/**
 * @author labvi
 * @version 1.0.0
 */
public class UniquePath {
    public static int uniquePathsWithObstacles(int[][] obstacleGrid) {
        // write your code here
        if (obstacleGrid == null) {
            return 0;
        }
        int col_num = obstacleGrid[0].length;
        int row_num = obstacleGrid.length;
        int[][] result = new int[row_num][col_num];
        result[0][0] = 1;
        for (int i = 1; i < col_num ;i++ ){
            if (obstacleGrid[0][i] == 1) {
                result[0][i] = 0;
            } else {
                result[0][i] = result[0][i-1];
            }
        }
        for (int j = 1; j < row_num ;j++ ){
            if (obstacleGrid[j][0] == 1) {
                result[j][0] = 0;
            } else {
                result[j][0] = result[j-1][0];
            }
        }

        for(int i = 1; i < row_num; i++){
            for(int j = 1;j < col_num;j++){
                if (obstacleGrid[i][j] == 1) {
                    result[i][j] = 0;
                }else {
                    result[i][j] = result[i][j-1] +
                            result[i-1][j];
                }
            }
        }
        return result[row_num-1][col_num-1];
    }

    public static void main(String[] args) {
        int[][] arr = {{0,0,0},{0,1,0},{0,0,0}};
        System.out.println(uniquePathsWithObstacles(arr));
    }
}
